package BackTrack.万诺;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
技巧：
    int resGan -> 造板 !!!!!!!

    1 正反都可 int [反着更符合dp
    2 return
       全要:
         内 rf()
         外     r;
    3 到末尾 才刚开始算[人任定值]
      (上方为 递归栈 存 i j tmp)

本题：【每点跳跃能力不同_跳至终点】

  * 只能从0走
    不能反向
        因为 能走的步数存在前面
        ->看草图红字

 */
public class 跳跃游戏_55_intRes干 {
    @Test
    public void test() {
//        int[] A = {2,3,1,1,4};
//        int[] A = {0,2,3};
//        int[] A = {2,0,0};
//        int[] A = {1,1,2,2,0,1,1};
        int[] A = {3,2,1,0,4};
        System.out.println(canJump(A));
    }

    // ac -> map题感走即可
    int[] v;
    int n;
    public boolean canJump(int[] nums) {
        v = nums;
        n = v.length;

//        int cI = nums.length-1-1; //不行，步数存在前一个弹簧处
        int cI = 0;
        return bT_resGan(cI);
    }

    private boolean bT_resGan(int cI) {
        // 末1开始算 [且人任意定值]
        if(cI >= n-1){
            return true;
        }

        boolean curCI_IsCanJumpFinal = false;
        for (int i = 1; i <= v[cI]; i++) {
            curCI_IsCanJumpFinal = curCI_IsCanJumpFinal
                    || bT_resGan(cI+i);
        }
        // r;
        return curCI_IsCanJumpFinal; // curCI 妙啊 出了[]DP思想
    }
}
